1. Field of the Invention
This invention relates to a cache memory capable of avoiding a fault of a cell even after it is installed in a system and an information processing system having the same cache memory.
2. Description of the Prior Art
The cache memory has been used as a high-speed buffer memory to accelerate memory access of a microprocessor and large-capacity cache memories have been loaded on the microprocessor because of increased program volume and improvement of micromachining technology in recent years.
In integrated cache memory in which a cache system can be formed with a single chip as well, its capacity has been increased more and more.
A structure of the conventional cache memory will be described with reference to FIG. 1.
The cache memory shown in FIG. 1 is a 4-way set associative type cache memory, which includes four tag memory arrays 101 and four data memory arrays 102. The memory array of each way is accessed according to a result of decoding of address lower bits by an address decoder 103 and the content of each memory cell is read by a read/write circuit 104a. A tag address read by a read/write circuit 104b from the tag memory array 101 is compared with upper level bits of address by a comparator 105 provided on each way. If as a result of comparison, there exists a way in which both coincide with each other so that that way is hit, access data is stored in the hit way. Data read from the data memory array 102 and then hit is selected by a way selector 106 and output. On the other hand if no coincidence is detected in all the ways so that cache miss occurs, the access data does not exist in the cache memory and therefore, an external memory is accessed.
From the viewpoints of timely/spatial localization of the memory access, it is most advantageous for system performance that data having a high access frequency is stored in the cache memory. Thus, if a cache miss occurs, one data stored in the cache is expelled and replace action for storing new data is performed. In such a replace action, LRU (Least Recently Used) algorithm is frequently used to determine which way data should be expelled and replaced with new data.
According to this LRU algorithm, which data has not been accessed recently of data stored in the cache is stored by LRU bit 107 and if cache miss occurs, data in the LRU bit 107 is read by a read/write circuit 113 and a way in which data should be replaced is determined with reference to the LRU bit. If pseudo LRU algorithm is used in, for example, 4-way set associative type, the LRU bit requires three bits. The LRU bit (LRU [0], [1], [2]) is rewritten by the read/write circuit 113 and updated according to a hit way as shown in Table 1 when it is hit.
TABLE 1 ______________________________________ hit way LRU [0] LRU [1] LRU [2] ______________________________________ 0 1 -- 1 1 0 -- 1 2 -- 1 0 3 -- 0 0 ______________________________________
On the other hand, if a cache miss occurs, a way to be updated is determined with reference to the aforementioned LRU bit read by the read/write circuit 113 as shown in Table 2.
TABLE 2 ______________________________________ Update way LRU [0] LRU [1] LRU [2] ______________________________________ 0 0 X 0 1 1 X 0 2 X 0 1 3 X 1 1 ______________________________________
In the cache memory, fault rate of the cell has been increasing with a tendency of increased scale of the memory capacity, so that a drop of the yield rate has been problematic. Then, to rescue a few faulty cells, in some cases, a redundant circuit usually used in general purpose DRAM or SRAM or the like is provided in the cache memory. According to this method, as shown in FIG. 1, extra memory cells 108 are disposed in the direction of word line (or direction of bit line). Further, a spare decoder 109 and LRU bit 110 are provided corresponding to this extra memory cells 108, so that when a faulty cell is found, a word line (or bit line) corresponding to the faulty cell is separated and an address of this separated word line (or bit line) is allocated to the extra memory cell. Separation of word line (or bit line) and changeover of the address to the extra disposed memory cell are carried out by cutting, for example, a fuse element 111 by laser. As a result, a few faulty cells are rescued so that the faulty product having the faulty cells can be converted to a good product, thereby relaxing the reduction of the yield rate.
The redundant circuits extra provided separately from regular circuits as a rescue way for the faulty cell cannot be provided in a large quantity not to affect the tendency of expanding structure. For the reason, only the faulty cells of the same number as that of provided redundant circuits, that is, a small number of the faulty cells can be rescued. Thus, if more faulty cells occur than a number of the redundant circuits provided, all the faulty cells cannot be rescued and in this case, that entire cache memory becomes a faulty product.
In addition, although the aforementioned rescue way is effective for a cell fault which occurs just after production of the memory, this way cannot be applied to a case in which the cache memory is installed in a system.